package com.atcumt.Carl.Dp;

import java.util.ArrayList;
import java.util.List;

public class BagProblem {

    // 01背包
    public static int BagProblem01 (int[] weight, int[] value, int bagWeight) {
        int n = weight.length;
        int[][] dp = new int[n + 1][bagWeight + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < bagWeight; j++) {
                if (j < weight[i - 1]) {
                    dp[i][j] = dp[i - 1][j]; // 不选物品 j
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i - 1]);
                }
            }
        }
        return dp[n][bagWeight];
    }

    // 01背包优化
    public static int BagProblem01_2 (int[] weight, int[] value, int bagWeight){
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                if (j >= weight[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
        return dp[weight.length];
    }

    // 完全背包
    public static int BagProblem02 (int[] weight, int[] value, int bagWeight) {
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = weight[i]; j <= bagWeight; j++) {
                if (j >= weight[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
        return dp[weight.length];
    }

    // 多重背包
    public static int BagProblem03 (int[] weight, int[] value, int bagWeight, int[] nums) {
        List<Integer> weightList = new ArrayList<>();
        List<Integer> valueList = new ArrayList<>();

        // 利用nums把数组摊开,weight数组存入 weightList，value数组存入 valueList
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0) {
                weightList.add(weight[i]);
                valueList.add(value[i]);
                nums[i]--;
            }
        }
        int n = weightList.size();
        int[][] dp = new int[n + 1][bagWeight + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= bagWeight; j++) {
                if (j < weightList.get(i - 1)) {
                    dp[i][j] = dp[i - 1][j]; // 不选物品 j
                } else {
                    dp[i][j] = Math.max(
                            dp[i - 1][j],
                            dp[i - 1][j - weightList.get(i - 1)] + valueList.get(i - 1)
                    );
                }
            }
        }
        return dp[n][bagWeight];
    }
}
